package com.xsherl.leetcode.solution;

import java.util.ArrayList;
import java.util.List;

public class RestoreIpAddresses {

    int[] path = new int[4];

    /**
     * 回溯 + 剪枝
     */
    public List<String> restoreIpAddresses(String s) {
        List<String> list = new ArrayList<>();
        if (s.length() < 4 || s.length() > 13){
            return list;
        }
        restoreIpAddresses(s, 0, 0, list);
        return list;
    }

    public void restoreIpAddresses(String s, int i, int count, List<String> res) {
        // 如果ip地址已经全部获取了, 并且字符串没有剩余，就加入结果中
        if (count == 4){
            if (i < s.length()){
                return;
            }
            StringBuilder sb = new StringBuilder();
            for (int m = 0; m < 4; ++m){
                sb.append(path[m]);
                if (m != 3){
                    sb.append(".");
                }
            }
            res.add(sb.toString());
            return;
        }
        int len = Math.min(s.length() - i, 3);
        int number = 0;
        for (int j = 0; j < len; ++j){
            number = number * 10 + (s.charAt(i + j) - '0');
            if (j > 0 && s.charAt(i) == '0'){
                return;
            }
            if (number <= 255){
                path[count] = number;
                restoreIpAddresses(s, i + j + 1, count + 1, res);
            }
        }
    }


    public static void main(String[] args) {
        String s = "00100";
        List<String> strings = new RestoreIpAddresses().restoreIpAddresses(s);
        System.out.println(strings);
    }
}
